package com.leetcode.程序员面试金典.hard;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 覃国强
 * @date 2021-09-06 12:43
 */
public class 面试题_08_12_八皇后 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    List<List<String>> lists = solution.solveNQueens(4);
    for (List<String> list : lists) {
      for (String str : list) {
        System.out.println(str);
      }
      System.out.println();
    }

  }

  static
  class Solution {
    public List<List<String>> solveNQueens(int n) {

      List<List<String>> result = new ArrayList<>();

      int[] queensIndex = new int[n];

      solveNQueens(queensIndex, 0, result);

      return result;
    }


    private void solveNQueens(int[] queensIndex, int curIndex, List<List<String>> result) {
      if (curIndex == queensIndex.length) {
        List<String> queens = generateQueens(queensIndex);
        result.add(queens);
        return;
      }
      for (int i = 0; i < queensIndex.length; ++i) {
        queensIndex[curIndex] = i;
        if (isValid(queensIndex, curIndex)) {
          solveNQueens(queensIndex, curIndex + 1, result);
        }
      }
    }

    private boolean isValid(int[] queensIndex, int curIndex) {
      // 列
      for (int i = 0; i < curIndex; ++i) {
        if (queensIndex[i] == queensIndex[curIndex]) {
          return false;
        }
      }
      // 左对角线
      for (int index = queensIndex[curIndex] + 1, i = curIndex - 1; index < queensIndex.length && i >= 0; ++index, --i) {
        if (queensIndex[i] == index) {
          return false;
        }
      }

      // 右对角线
      for (int index = queensIndex[curIndex] - 1, i = curIndex - 1; index >= 0 && i >= 0; --index, --i) {
        if (queensIndex[i] == index) {
          return false;
        }
      }

      return true;
    }

    private List<String> generateQueens(int[] queensIndex) {
      List<String> result = new ArrayList<>();

      for (int i = 0; i < queensIndex.length; ++i) {
        StringBuilder rowBuilder = new StringBuilder();
        for (int j = 0; j < queensIndex.length; ++j) {
          rowBuilder.append('.');
        }
        rowBuilder.setCharAt(queensIndex[i], 'Q');
        result.add(rowBuilder.toString());
      }

      return result;
    }

  }

}
